On the set covering polytope: Facets with coefficients in {0,1,2,3}

M. Sánchez-García, M.I. Sobrón, B. Vitoriano

Annals of Operations Research Vol. 81, pp. 343 - 356

Resumen:

Balas and Ng[1,2] characterized the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and gave necessary and sufficient conditions for such an inequality to be facet defining. We extend this study, characterizing the class of valid inequalities with coefficients equal to 0,1,2 or 3, and giving necesary and sufficient conditions for such an inequality to be not dominated, and to be facet defining.

Palabras Clave: Set covering, facets, polyhedral combinatorics, combinatorial optimization

Índice de impacto JCR y cuartil WoS: 4,400 - Q1 (2023)

Referencia DOI: https://doi.org/10.1023/A:1018969410431

Publicado en papel: Junio 1998.

Cita:
M. Sánchez-García, M.I. Sobrón, B. Vitoriano, On the set covering polytope: Facets with coefficients in {0,1,2,3}. Annals of Operations Research. Vol. 81, pp. 343 - 356, Junio 1998.